BUBBLE SORTING Bubble sort is a routine designed to sort any number of elements in an array. The word 'BUBBLE' refers to the way in which the data item works its way up the list until they are in ascending or descending order. The algorithm for sorting an array is as follows: STEP 1. Examine the first two elements in the array STEP 2. If they are not in order then change (SWAP) them (Do nothing if they are in order). STEP 3. Go to the next pair of elements (EXAMPLE: If you were examining elements 1 & 2, you would NOW be looking at elements 2 & 3). STEP 4. Repeat STEP 2 and 3 until the last two elements in the array have been compared. At this point the largest element in the list has 'BUBBLED' up the list so that it is now the last item in the list. STEP 5. Repeat the entire procedure for the first n-1 elements in the array (n is the total number of elements in the array). At this point the second largest element in the array will be second to last. Keep repeating this ( use n-2, n-3, n-4, ... n-[n-1]) until the entire array is sorted. The bubble sort technique requires approx. ½ * N² operations (N is the total number of elements in the array). As the array size increases, the sorting time increases greatly. The bubble sorting algorithm listed above can be easily translated into any computer language code. The following page displays a bubble sorting program written in Quick BASIC (Please remember that there are many different ways to translate any given algorithm). The following variables are used in the Quick BASIC program listed on the next page: ARR$ = Array of type string used to store the data items. ARRAY.SIZE = Integer variable containing the size of the array. I = Integer index variable used showing the number of comparisons made during each pass. PASSES = Integer variable used in FOR-LOOP showing the total number of passes made in the array. REM Bubble sorting program FOR passes = 1 TO array.size-1 ' STEPS 1. & 5. FOR i = 1 TO array.size - passes ' One less comparison each LOOP. IF arr$(i) > arr$(i + 1) THEN ' STEP 2. SWAP arr$(i), arr$(i+1) ' Swap if not in order. END IF NEXT i ' STEP 3. & 4. NEXT passes ' STEP 5. REM End of BUBBLE SORT
